# 普通递归（指数级复杂度 O(2^n)）
def fib_recursive(n):
    return n if n <= 1 else fib_recursive(n - 1) + fib_recursive(n - 2)


# 带记忆化的DP版本（线性复杂度 O(n)）
mem = {}


def fib_memo(n):
    if n in mem:
        return mem[n]
    if n <= 1:
        return n
    mem[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return mem[n]


if __name__ == "__main__":
    recursive = fib_recursive(20)
    print(recursive)
    memo = fib_memo(20)
    print(memo)
